package com.hjx.leetcode;

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 示例 1:
 *
 *  输入: "()"
 *  输出: true
 * 示例 2:
 *
 *  输入: "()[]{}"
 *  输出: true
 * 示例 3:
 *
 *  输入: "(]"
 *  输出: false
 * 示例 4:
 *
 *  输入: "([)]"
 *  输出: false
 * 示例 5:
 *
 *  输入: "{[]}"
 *  输出: true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class LeetCode_20 {

    /**
     * 不成熟的想法，原本的想法为
     * 1、递归判定两个对应括号中间的内容是否合法，若合法则从后一个括号index+1处开始截取字符串
     * 2、对字符串重复步骤1，直到最后
     * 这种方法看似可行，但问题在于 如何判断两个括号是对应的 如："([()])" 按顺序扫描字符 可能得到 index=3处的')' 是 index=0处'('的对应 这是不对的
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        boolean isValid = true;
        if(s != null && s.length() == 0) {
            return true;
        } else {
            char left = s.charAt(0);
            char right;
            if (left == '(') {
                right = ')';
            } else if(left == '['){
                right = ']';
            } else {
                right = '}';
            }

            int newIndex = 0;
            for (int i = 1; i < s.length(); i++) {
                //找到右侧对应
                if (s.charAt(i) == right) {
                    //判定左右括号之间的字符串是否合法, 非法直接返回
                    isValid = isValid(s.substring(1, i));
                    if (!isValid) {
                        return false;
                    } else {
                        newIndex = i + 1;
                    }
                }
            }

            for (int j = newIndex; j < s.length(); j++) {

            }
        }
        return isValid;

    }

    /**
     *
     *
     * 执行用时：2 ms, 在所有 Java 提交中击败了76.57%的用户
     * 内存消耗：36.3 MB, 在所有 Java 提交中击败了98.01%的用户
     *
     * @param s
     * @return
     */

    public boolean isValid2(String s) {
        //字符串为null
        if (s == null) return false;
        //字符串长度为奇数
        if (s.length() % 2 == 1) return false;

        Stack<Character> stack = new Stack<>();
        //开始遍历
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            //左括号入栈
            if(map(temp) == '\0') {
                stack.push(temp);
            } else {
                // 非左括号 和栈顶元素对比  此时栈为空 或 栈顶元素 不是temp对应的左括号 则直接返回异常
                if(stack.isEmpty() || stack.peek() != map(temp)) {
                    return false;
                }
                //栈顶元素是 temp对应的左括号 出栈
                stack.pop();
            }
        }


        //遍历结束 栈空 则为合法
        return stack.size() == 0;
    }

    private char map(char ch) {
        char ret;
        switch (ch) {
            case ')':
                ret = '(';
                break;
            case ']':
                ret = '[';
                break;
            case '}':
                ret ='{';
                break;
            default:
                ret = '\0';
        }
        return ret;
    }
}
